import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:张熳
 * Date:2025-11-21
 * Time:14:33
 */
//使用堆模拟实现优先级队列：堆是一棵完全二叉树，以层序的规则采用顺序的方式来高效存储(使用数组村相互)
public class TestHeap {
    public int[] elem;
    public int usedSize;

    public int[] getElem() {
        return elem;
    }

    public int getUsedSize() {
        return usedSize;
    }

    //指定堆的空间大小
    public TestHeap() {
        this.elem = new int[10];
    }

    //初始化堆
    public void initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            usedSize++;
        }
    }

    //创建堆（以创建 大根堆）
    //思路：采用向下调整的方法创建大根堆，所谓向下调整就是将整个无序数组视为一个完全二叉树，从最后一个非叶子节点开始，向前遍历并对每个节点执行向下调整
    //(最后一个非叶子节点开始，从右到左)；从当前节点向下与子节点比较并交换。
    //在createHeap方法中，使用for循环调整堆，先确定最后一个非叶子节点parent父节点的位置，该位置为起始位置,
    //在parent大于等于根节点下标(0)时，即parent合法时，从当前节点parent向下与其左右子节点child比较并交换：
    //在siftDown方法中，先确定parent的左孩子child的下标位置，在左孩子存在的情况下(child<usedSize)，进入循环，如果parent的右孩子存在
    //(child+1<usedSize)，将左右孩子进行比较，找到两者之间较大的，如果左孩子大，则child下标位置不变(原先就是确定的左孩子的位置)，如果右孩子大，
    //则child++，走到右孩子的位置，此时的child标记的就是最大孩子的下标。接着比较parent和child，如果elem[child]>elem[parent]，即需要将
    //parent与较大的child交换(使用临时变量tmp辅助交换)，交换完成之后parent往下移动，即走到此时较大的child位置，然后继续确定此时新的parent的
    //左孩子的下标位置（注意，parent往下移动，可能会造成子树不满足大根堆的性质，因此需要继续向下调整）；如果elem[child]<elem[parent]，即
    //parent比最大的child还大，说明该结构已经满足大根堆的性质，直接break跳出循环。
    //再次回到createHeap方法中，parent--，走到倒数第二个非叶子节点处，再次开始让当前parent与左右孩子child比较，即进入siftDown方法中。
    //建堆的时间复杂度：O(N)
    public void createHeap() {
        for (int parent = (this.usedSize-1-1)/2; parent >= 0 ; parent--) {
            siftDown(parent,this.usedSize);
        }
    }
    //向下调整 方法
    //parent 表示每棵子树调整的时候的起始位置
    //usedSize 表示判断每棵子树什么时候调整结束
    //堆向下调整的时间复杂度：最坏的情况是从根一路比较到叶子，比较的次数为完全二叉树的高度，时间复杂度为O(log_2N)
    private void siftDown(int parent,int usedSize) {
        int child = 2*parent+1;
        while (child < usedSize) {
            //找到左右孩子中的最大值
            if (child+1 < usedSize && elem[child] < elem[child+1]) {
                child++;
            }
            if (elem[child] > elem[parent]) {
                /*
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                */
                swap(elem,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }
    public void swap(int[] elem,int i,int j) {
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }

    //向下调整创建小根堆
    public void createHeap1() {
        for (int parent = (this.usedSize-1-1)/2; parent >= 0 ; parent--) {
            siftDown1(parent,usedSize);
        }
    }
    public void siftDown1(int parent,int usedSize) {
        int child = 2*parent+1;
        while (child < usedSize) {
            //如果右孩子存在，找到左右孩子中较小的孩子,用child进行标记
            if (child+1 < usedSize && elem[child] > elem[child+1]) {
                child++;
            }
            if (elem[child] < elem[parent]) {
                //将双亲与较小的孩子交换
                swap(elem,child,parent);
                //parent中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
                parent = child;
                child = 2*parent+1;
            }else {
                //如果双亲比其最小的孩子还小，说明该结构已经满足堆的特性了
                break;
            }
        }
    }

    //堆的插入(大根堆调整) - 插入优先级最高的元素
    //堆的插入总共需要两个步骤：1.先将元素插入到堆的末尾，即最后一个孩子的后面(空间不够时需要扩容)  2.将最后新插入的节点向上调整，直到满足堆的性质
    //注意：这里插入新节点后，要用的是 向上调整 的方法来将该节点顺着其双亲节点往上调整到合适的位置
    //思路：在offer方法中，先判断堆是否已满，如果满了，则需要扩容；往堆的末尾usedSize处插入新节点，即插入新孩子节点child，进入siftUp方法：
    //在该方法中，首先确定child的双亲节点parent，在child合法的情况下，即child大于根节点下标(0)时(child=0时已是根节点，无需再调整)，进入循环，
    //如果elem[child]>elem[parent]，则两者进行交换，交换完成之后，child走到parent的位置，然后确定新的parent的下标位置(交换完成之后，
    //大的元素向上走，小的元素向下移动，可能会造成子树不满足堆的性质，因此需要继续向上调整)，如果elem[child]<elem[parent]，即parent比child大
    //parent满足堆的性质，调整结束，跳出循环。
    //回到offer方法中，此时的新child插入并向上调整结束，usedSize++。
    public void offer(int val) {
        if (isFull()) {
            //扩容
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize] = val;
        siftUp(usedSize);
        usedSize++;
    }
    public boolean isFull() {
        return usedSize == elem.length;
    }

    //向上调整 方法
    //所谓向上调整就是从空堆开始，逐个插入元素。每插入一个，就对该元素执行向上调整（第一个元素开始，从左到右）；从新插入的叶子节点向上
    //与父节点比较并交换。
    //堆向上调整的时间复杂度：最坏的情况是从叶子一路比较到根，比较的次数为完全二叉树的高度，时间复杂度为O(log_2N)
    private void siftUp(int child) {
        //确定child的双亲parent
        int parent = (child-1)/2;
        while (child > 0) {
            if (elem[child] > elem[parent]) {
                //如果child大于parent，将两者进行交换
                swap(elem,child,parent);
                //交换完成之后，大的元素向上走，小的元素向下移动，可能会造成子树不满足堆的性质，因此需要继续向上调整
                child = parent;
                parent = (child-1)/2;
            }else {
                //如果child<parent，parent满足堆的性质(是大堆或者是小堆)，调整结束
                break;
            }
        }
    }

    //堆的插入(小根堆调整)
    public void offer1(int val) {
        if (isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize] = val;
        siftUp1(usedSize);
        usedSize++;
    }
    public void siftUp1(int child) {
        int parent = (child-1)/2;
        while (child > 0) {
            if (elem[child] < elem[parent]) {
                swap(elem,child,parent);
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }

    //堆的删除(删除优先级最高的元素)
    //堆的删除一定删除的是堆顶元素。具体做法：
    //1.将堆顶元素与堆中最后一个元素进行交换 2.删除堆中最后一个元素，即将堆中有效元素个数减少一个 3.将堆顶元素进行向下调整直到满足堆的特性为止
    public int poll() {
        if (isEmpty()) {
            return -1;
        }
        int val = elem[0];
        swap(elem,0,usedSize-1);
        siftDown(0,usedSize-1);//交换完成之后，堆中最后一个元素就直接被删除了，即堆的空间大小为usedSize-1
        usedSize--;
        return val;
    }
    public boolean isEmpty() {
        return usedSize == 0;
    }

    //获取堆中优先级最高的元素/堆顶元素
    public int peek() {
        if (isEmpty()) {
            return -1;
        }
        return elem[0];
    }

    //堆排序
    //堆排序即利用堆的思想来进行排序，总共分为两个步骤：
    //1.建堆：如果想将堆变成升序排序-建大堆、想将堆变成降序排序-建小堆
    //2.利用堆删除的思想进行排序-建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
    //思路(以大根堆为例)：建立完大根堆后，将堆顶元素与堆中最后一个元素end交换位置，然后从此时的堆顶元素开始向下调整，直到重新符合堆的性质，接着让
    //end--，走到堆中倒数第二个元素的位置end，再让重新调整好后的堆顶元素与此时的end交换位置，然后从此时的堆顶元素开始向下调整，直到重新符合堆的性质
    //重复上述的操作，直到end走到根节点的位置(0)，停止，说明堆已经调整完成，此时的堆是一个升序排序的堆。
    //（降序排序的思路一样）
    public void heapSort() {
        int end = usedSize-1;
        while (end > 0) {
            swap(elem,0,end);
            siftDown(0,end);
            end--;
        }
    }
    //堆排序的时间复杂度：O(n*log_2n)
    //降序
    public void heapSort1() {
        int end = usedSize-1;
        while (end > 0) {
            swap(elem,0,end);
            siftDown1(0,end);
            end--;
        }
    }
}
